class Solution {//leetcode215——数组中第k个最大元素
private:
    void _swap(int& lhs,int& rhs){
        int tmp=lhs;
        lhs=rhs;
        rhs=tmp;
    }
    int q_serch(vector<int>nums,int begin,int end,int k){
        if(begin==end) return nums[begin]; 

        int left=begin-1,right=end+1,i=begin;
        int key=randomNum(nums,begin,end);
        while(i<right){
            if(nums[i]<key) _swap(nums[i++],nums[++left]);
            else if(nums[i]==key) i++;
            else _swap(nums[i],nums[--right]);
        }
        int b=right-left-1,c=end-right+1;
        if(c>=k) return q_serch(nums,right,end,k);
        else if(b+c>=k) return key;
        else  return q_serch(nums,begin,left,k-(b+c));
    }
    int randomNum(vector<int>nums,int begin,int end){//在nums的[begin,end]中随机一个元素作为key值
        int keyi=rand()%(end-begin+1)+begin;
        return nums[keyi];
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand((unsigned int)time(nullptr));
        return q_serch(nums,0,nums.size()-1,k);
    }
};